The present invention relates generally to computer systems and, more particularly, to a method and system for handling broadcast queue overflow during in-cache garbage collection.
As is known to those skilled in the art, garbage collection is the automatic management of dynamically allocated memory storage. Generally speaking, the process performing the garbage collection, i.e., the garbage collector, automatically reclaims dynamically allocated memory on a periodic basis. In addition, certain events may trigger garbage collection. For example, if the amount of unallocated memory is below a threshold value during a memory allocation process, then garbage collection may be triggered. During garbage collection, the executing program typically is suspended. The executing program is allowed to resume when garbage collection has been completed.
Before a dynamically allocated piece of memory can be reclaimed, the garbage collector must ensure that the data in the piece of memory to be reclaimed is not live. As used in the context of garbage collection, the term “live” refers to a piece of memory containing data that is required by an executing program or data that is reachable by following a path of pointers from a root, i.e., a memory location that is always deemed as live. Those skilled in the art are familiar with a number of algorithms that may be used to reclaim dynamically allocated pieces of memory. One such algorithm is the Mark-Sweep algorithm (see “John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Communications of the ACM, 3:184–195, 1960”). The Mark-Sweep algorithm is performed in two phases. The first phase is the marking phase in which a recursive traversal is performed to find all pieces of memory connected directly or indirectly to the roots. Each piece of memory encountered in the recursive traversal is marked as live. The second phase is the sweep phase during which any piece of memory that is not marked as live is reclaimed.
During an in-cache garbage collection process, the various processors within the garbage collection (GC) boundary scan their own caches and perhaps part of any shared caches and broadcast to all caches any references to objects found to be live so that other processors can mark those objects and scan them. This marking is performed by a hardware operation that places the object identifier (OID) of the object found to be live in a queue of the cache that contains that object's header.
The length of the queue is theoretically bounded only by the number of cache lines present in the cache. It is impractical and inefficient for this hardware structure to be large enough to accommodate all the cache lines in the cache. The use of a smaller hardware structure, however, would make it likely that the queue would overflow at some point during the marking process.
In view of the foregoing, there is a need for a method for handling queue overflow during in-cache garbage collection so that a smaller-sized hardware structure can be used in the marking phase.